package dp.beibao;

/**
 * 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
 *
 * 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
 *
 * 示例：
 *
 * 输入：nums: [1, 1, 1, 1, 1], S: 3 输出：5 解释：
 *
 * -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3
 *
 * 一共有5种方法让最终目标和为3。
 *
 * 提示：
 *
 * 数组非空，且长度不会超过 20 。
 * 初始的数组的和不会超过 1000 。
 * 保证返回的最终结果能被 32 位整数存下
 */
public class leetCode494_FindTargetSumWays {
    /**
     * 既然为target，那么就一定有 left组合 - right组合 = target。
     *
     * left + right等于sum，而sum是固定的。
     *
     * 公式来了， left - (sum - left) = target ->  left = (target + sum)/2
     *
     * 重新写一下 x = (target + sum)/2
     * if ((S + sum) % 2 == 1) return 0; // 此时没有方案
     * 所以套在背包问题上
     *
     * x 是背包的容量  数字就是物品  数字大小就是每个物品的重量
     *
     * 原始的01背包求是的最大值，而这次求的是组合个数。
     * 求最大值用
     * dp[j] = Math.max(dp[j],dp[j-weight[i]] + value[1])
     *
     * 求组合用 （dp[i] 表示 填满j（包括j）这么大容积的包，有dp[i]种方法）
     * dp[j] += dp[j - nums[i]]
     *
     * @param nums
     * @param target
     * @return
     */
    public static int findTargetSumWays(int[] nums, int target) {
        if(nums.length == 0) {
            return 0;
        }
        if(nums.length == 1
                && nums[0] != target
                && ((nums[0] + target) != 0)){
            return 0;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 公式
        if((target + sum)%2 == 1){
            return 0;
        }
        int x = (target + sum)/2;
        int[] f = new int[x+1];
        f[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = x; j >= nums[i]; j--) {
                f[j] += f[j - nums[i]];
            }
        }
        return f[x];
    }

    public static void main(String[] args) {
        int[] nums = {1};
        int target = 1;
        int targetSumWays = findTargetSumWays(nums, target);
    }

    /**
     * 既然为target，那么就一定有 left组合 - right组合 = target。
     *
     * left + right等于sum，而sum是固定的。
     *
     * 公式来了， left - (sum - left) = target ->  left = (target + sum)/2 。
     *
     * target是固定的，sum是固定的，left就可以求出来。
     *
     * 此时问题就是在集合nums中找出和为left的组合。
     * @param nums
     * @param target
     * @return
     */
    public static int findTargetSumWays2 (int[] nums, int target) {

        if(nums.length == 0) return 0;
        if(nums.length == 1
                && nums[0] != target
                && ((nums[0] + target) != 0)){
            return 0;
        }
        int sum = 0;

        for (int num : nums) {
            sum += num;
        }

        if((sum + target)%2 == 1){
            return 0;
        }

        /**
         * 例如sum 是5，S是2的话其实就是无解的，所以：
         *
         * if ((S + sum) % 2 == 1) return 0; // 此时没有方案
         */

        int x = (target + sum)/2;

        int[] dp = new int[x + 1];

        dp[0] = 1;
        for (int num : nums) {
            for (int j = x; j >= num ; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[x];




    }
}
